package datastructure.sort_algorithm;

import java.util.Arrays;

/**
 * 归并排序
 * O(n log n)
 * @author lbw
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        System.out.println(Arrays.toString(mergeSort(arr)));

    }

    public static int[] mergeSort(int[] sourceArr){
        int[] arr = Arrays.copyOf(sourceArr, sourceArr.length);
        if (arr.length < 2){
            return arr;
        }
        //找中间数拆分为左右数组
        int middle = (int) Math.floor(arr.length / 2);
        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);
        //将左右数组也一直拆分，直到剩余一个元素后进行合并
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 合并
     */
    public static int[] merge(int[] left, int[] right){
        int[] result = new int[left.length + right.length];
        int i = 0;
        //循环中left和right的值会不断缩小，当某一个数组的元素为0时说明已经全部放入到了有序数组中，直接将另外一个的一次放入即可
        while (left.length > 0 && right.length > 0){
            //两边的元素进行比较，将值小的元素放入到临时数组中，同时将该元素所在的数组重新赋值 等价于下标+1
            if (left[0] <= right[0]){
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
        //将剩余的数组的值依次放入到result中
        while (left.length > 0){
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0){
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }
}
